Data Processing Inequality

Formula of diminishing influence.

Formula

$\begin{aligned} X \to Y \to Z \Rightarrow I(X; Y) \geq I(X; Z) \end{aligned}$

Proof

$\begin{aligned} I(X; Y, Z) &= I(X; Z) + I(X; Y | Z) \\ &= I(X; Y) + I(X; Z | Y) \\ \because I(X;Z|Y) &= 0 \left(\log \frac{P[X;Z|Y]}{P[X|Y] \cdot P[Z|Y]} = \log \frac{P[Z|X,Y] \cdot P[X|Y]}{P[X|Y] \cdot P[Z|Y]} = \log 1 = 0 \right ) \\ \therefore I(X; Y) &= I(X; Z) + I(X; Y | Z) \geq I(X; Z) \end{aligned}$

Usage

$\begin{aligned} I(X;Z) &= H(X) - H(X | Z) \\ &\leq H(X) - H(X|Y) = I(X; Y) \\ \Longrightarrow H(X|Z) &\geq H(X|Y) \end{aligned}$

Interpretation

• $Z$ has its own freedom. But part of it comes from $Y$.
• $I(X;Z|Y) = 0$: No additional information gained for $X$ from $Z$ if $Y$ is known.
• $I(X; Z)$: Degree of relevance. Information gained from $Z$ for $X$.
  • Less than the information that can be gained from $Y$.
• $H(X|Z)$: Uncertainty of $X$ with additional information from $Z$.
  • Greater than that when having additional information from $Y$.

by Jon